#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


class Solution {
public:
	string digit[10];
	vector<string> ret;
	void init(){
		
		digit[2]="abc";
		digit[3]="def";
		digit[4]="ghi";
		digit[5]="jkl";
		digit[6]="mno";
		digit[7]="pqrs";
		digit[8]="tuv";
		digit[9]="wxyz";
	}
	void dfs(string digits,int nPos,string sCur){
		
		if(nPos==digits.size()){
			
			if(sCur.size()){
				
				ret.push_back(sCur);
			}
			return;
		}
		int nIdx=digits[nPos]-'0';
		for(int i=0;i<digit[nIdx].size();++i){
			
			sCur.push_back(digit[nIdx][i]);
			dfs(digits,nPos+1,sCur);
			sCur.pop_back();
		}
	}
    vector<string> letterCombinations(string digits) {
        
        init();
        dfs(digits,0,"");
        return ret;
    }
};
